home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11926 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.1 KB
  1. Path: mayne.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: "Best fit" algorithm (help)
  5. Date: 27 Mar 1996 10:04:26 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4jbvvaINNsqi@mayne.ugrad.cs.ubc.ca>
  8. References: <APC&7'0'22b6b83'874@peg.apc.org> <4j9215INNgbo@keats.ugrad.cs.ubc.ca> <4jbb9d$g14@news.xs4all.nl>
  9. NNTP-Posting-Host: mayne.ugrad.cs.ubc.ca
  10.  
  11. In article <4jbb9d$g14@news.xs4all.nl>, Falstaff <falstaff@xs4all.nl> wrote:
  12. >c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) writes:
  13. >
  14. >> >I am looking for a "best fit" algorithm. 
  15. >> >The problem I have is very similar to finding the best way of fitting the 
  16. >> >maximum number of songs on (say) 45 minute tape.
  17. >
  18. >>Assuming that you don't care _which_ songs go on the tape, try a ``greedy''
  19. >>approach. Always add to the tape a song which will leave the most free space.
  20. >
  21. >>This means starting with the smallest one, and adding the next bigger one and
  22. >>so on. This should yield an optimal solution for the constraint of maximizing
  23. >>the number of songs that go on the tape. It won't minimize the left-over space,
  24. >>however.
  25. >
  26. >Hmmm.  I think the user wants to minimize just that (unused space).
  27.  
  28. The quoted paragraph clearly states an objective involving the maximum _number_
  29. of songs, as well as the objective of finding a good fit.
  30.  
  31. >To do that, you should pick the *largest* item that will still fit.
  32.  
  33. Such a greedy strategy will unfortunately exhaust the available space using the
  34. least number of songs. You also need to implement some sort of backtracking to
  35. find the optimal solution.
  36.  
  37. >Knuth (?) has proof that this is guaranteed to use less than twice
  38. >the minimum possible space to fit all items, and *likely* to use
  39. >much less than that maximum.
  40.  
  41. That is also the approach to solving the knapsack problem, with the added
  42. copmlexity that the selected integers have to add up to _exactly_ the given
  43. amount. You use backtracking to get out of impossible situations, so in effect
  44. you are traversing a tree of choices at the root of which you have the decision
  45. of including or not including the largest integers. The general solution is
  46. NP-complete, but for certain sequences of integers, the solution is trivial.
  47. Such sequences are ones in which the next largest item is bigger than the sum
  48. of the previous items. The simplest such series is the powers of two.
  49.  
  50. 2    > 1
  51. 4    > 2 + 1
  52. 8    > 4 + 2 + 1
  53.  
  54. etc.
  55.  
  56. In such a series, if you _can_ include the largest number in the sum, you
  57. simply include and forget about it. No backtracking is needed and you reach the
  58. leaf of the decision tree in O(log n) time.
  59.  
  60. Suppose that some combination or combinations of the songs will cover the tape
  61. exactly. Then a search for these optimal solutions is the same as a search for
  62. the solution to the knapsack problem. Simply choosing the largest song that
  63. will fit into the remaining space, without allowing for backtracking, will not
  64. find the general solution for this special case which we know is equivalent to
  65. the knapsack problem; since it doesn't solve some instances of the special
  66. case optimally, it cannot be a general solution.
  67.  
  68.  
  69.  
  70. -- 
  71.  
  72.